<html lang="zh-CN"><head><meta charset="UTF-8"><style>.nodata  main {width:1000px;margin: auto;}</style></head><body class="nodata " style=""><div class="main_father clearfix d-flex justify-content-center " style="height:100%;"> <div class="container clearfix " id="mainBox"><main><div class="blog-content-box">
<div class="article-header-box">
<div class="article-header">
<div class="article-title-box">
<h1 class="title-article" id="articleContentId">(A卷,200分)- 最优资源分配（Java & JS & Python）</h1>
</div>
</div>
</div>
<div id="blogHuaweiyunAdvert"></div>

        <div id="article_content" class="article_content clearfix">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/kdoc_html_views-1a98987dfd.css">
        <link rel="stylesheet" href="https://csdnimg.cn/release/blogv2/dist/mdeditor/css/editerView/ck_htmledit_views-044f2cf1dc.css">
                <div id="content_views" class="htmledit_views">
                    <h4 id="main-toc">题目描述</h4> 
<p>某块业务芯片最小容量单位为1.25G&#xff0c;总容量为M*1.25G&#xff0c;对该芯片资源编号为1&#xff0c;2&#xff0c;...&#xff0c;M。该芯片支持3种不同的配置&#xff0c;分别为A、B、C。</p> 
<ul><li>配置A&#xff1a;占用容量为 1.25 * 1 &#61; 1.25G</li><li>配置B&#xff1a;占用容量为 1.25 * 2 &#61; 2.5G</li><li>配置C&#xff1a;占用容量为 1.25 * 8 &#61; 10G</li></ul> 
<p>某块板卡上集成了N块上述芯片&#xff0c;对芯片编号为1&#xff0c;2&#xff0c;...&#xff0c;N&#xff0c;各个芯片之间彼此独立&#xff0c;不能跨芯片占用资源。</p> 
<p>给定板卡上芯片数量N、每块芯片容量M、用户按次序配置后&#xff0c;请输出芯片资源占用情况&#xff0c;保证消耗的芯片数量最少。</p> 
<p></p> 
<p>资源分配规则&#xff1a;按照芯片编号从小到大分配所需资源&#xff0c;芯片上资源如果被占用标记为1&#xff0c;没有被占用标记为0.</p> 
<p>用户配置序列&#xff1a;用户配置是按次序依次配置到芯片中&#xff0c;如果用户配置序列种某个配置超过了芯片总容量&#xff0c;丢弃该配置&#xff0c;继续遍历用户后续配置。</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%85%A5%E6%8F%8F%E8%BF%B0">输入描述</h4> 
<p>M&#xff1a;每块芯片容量为 M * 1.25G&#xff0c;取值范围为&#xff1a;1~256</p> 
<p>N&#xff1a;每块板卡包含芯片数量&#xff0c;取值范围为1~32</p> 
<p>用户配置序列&#xff1a;例如ACABA&#xff0c;长度不超过1000</p> 
<p></p> 
<h4 id="%E8%BE%93%E5%87%BA%E6%8F%8F%E8%BF%B0">输出描述</h4> 
<p>板卡上每块芯片的占用情况</p> 
<p></p> 
<h4>备注</h4> 
<p>用户配置是按次序依次配置到芯片中&#xff0c;如果用户配置序列种某个配置超过了芯片总容量&#xff0c;丢弃该配置&#xff0c;继续遍历用户后续配置。</p> 
<p></p> 
<h4 id="%E7%94%A8%E4%BE%8B">用例</h4> 
<table border="1" cellpadding="1" cellspacing="1" style="width:570px;"><tbody><tr><td style="width:53px;">输入</td><td style="width:515px;">8<br /> 2<br /> ACABA</td></tr><tr><td style="width:53px;">输出</td><td style="width:515px;">11111000<br /> 11111111</td></tr><tr><td style="width:53px;">说明</td><td style="width:515px;"> <p>用户第1个配置A&#xff1a;占用第1块芯片第1个资源&#xff0c;芯片占用情况为&#xff1a;</p> <p>10000000</p> <p>00000000</p> <p>用户第2个配置C&#xff1a;第1块芯片剩余8.75G&#xff0c;配置C容量不够&#xff0c;只能占用第2块芯片&#xff0c;芯片占用情况为&#xff1a;</p> <p>10000000</p> <p>11111111</p> <p>用户第3个配置A&#xff1a;第1块芯片剩余8.75G&#xff0c;还能继续配置&#xff0c;占用第1块芯片第2个资源&#xff0c;芯片占用情况为&#xff1a;</p> <p>11000000</p> <p>11111111</p> <p>用户第4个配置B&#xff1a;第1块芯片剩余7.5G&#xff0c;还能继续配置&#xff0c;占用第1块芯片第3、4个资源&#xff0c;芯片占用情况为&#xff1a;</p> <p>11110000</p> <p>11111111</p> <p>用户第5个配置A&#xff1a;第1块芯片剩余5G&#xff0c;还能继续配置&#xff0c;占用第1块芯片第5个资源&#xff0c;芯片占用情况为&#xff1a;</p> <p>11111000</p> <p>11111111</p> </td></tr></tbody></table> 
<table border="1" cellpadding="1" cellspacing="1" style="width:570px;"><tbody><tr><td style="width:54px;">输入</td><td style="width:514px;">8<br /> 2<br /> ACBCB</td></tr><tr><td style="width:54px;">输出</td><td style="width:514px;">11111000<br /> 11111111</td></tr><tr><td style="width:54px;">说明</td><td style="width:514px;"> <p>用户第1个配置A&#xff1a;占用第1块芯片第1个资源&#xff0c;芯片占用情况为&#xff1a;</p> <p>10000000</p> <p>00000000</p> <p>用户第2个配置C&#xff1a;第1块芯片剩余8.75G&#xff0c;配置C容量不够&#xff0c;只能占用第2块芯片&#xff0c;芯片占用情况为&#xff1a;</p> <p>10000000</p> <p>11111111</p> <p>用户第3个配置B&#xff1a;第1块芯片剩余8.75G&#xff0c;还能继续配置&#xff0c;占用第1块芯片第2、3个资源&#xff0c;芯片占用情况为&#xff1a;</p> <p>11100000</p> <p>11111111</p> <p>用户第4个配置C&#xff1a;芯片资源不够&#xff0c;丢弃配置&#xff0c;继续下一个配置&#xff0c;本次配置后芯片占用情况保持不变&#xff1a;</p> <p>11100000</p> <p>11111111</p> <p>用户第5个配置B&#xff1a;第1块芯片剩余6.25G,还能继续配置&#xff0c;占用第1块芯片第4、5个资源&#xff0c;芯片占用情况为&#xff1a;</p> <p>11111000</p> <p>11111111</p> </td></tr></tbody></table> 
<h4 id="%E9%A2%98%E7%9B%AE%E8%A7%A3%E6%9E%90">题目解析</h4> 
<p>本题输出比较难以理解&#xff0c;我这里以用例1解释一下&#xff1a;</p> 
<p>用例1的前两行输入表示&#xff1a;</p> 
<p>板卡上有N&#61;2个芯片&#xff0c;而每个芯片有8个单位容量&#xff0c;因此对应如下&#xff1a;</p> 
<blockquote> 
 <p>00000000</p> 
 <p>00000000</p> 
</blockquote> 
<p>其中每个0代表一个单位容量&#xff0c;而一个芯片有8单位容量&#xff0c;因此第一排8个0代表一个芯片的总容量&#xff0c;第二排8个0代表另一个芯片的总容量。</p> 
<p>理解了这个&#xff0c;本题就不难了。</p> 
<p></p> 
<h4 id="%E7%AE%97%E6%B3%95%E6%BA%90%E7%A0%81">JavaScript算法源码</h4> 
<pre><code class="language-javascript">/* JavaScript Node ACM模式 控制台输入获取 */
const readline &#61; require(&#34;readline&#34;);

const rl &#61; readline.createInterface({
  input: process.stdin,
  output: process.stdout,
});

const lines &#61; [];
rl.on(&#34;line&#34;, (line) &#61;&gt; {
  lines.push(line);

  if (lines.length &#61;&#61;&#61; 3) {
    let m &#61; lines[0] - 0;
    let n &#61; lines[1] - 0;
    let sequence &#61; lines[2];

    getResult(m, n, sequence);
    lines.length &#61; 0;
  }
});

function getResult(m, n, sequence) {
  boardCard &#61; new Array(n).fill(0).map(() &#61;&gt; m * 1.25);

  dict &#61; { A: 1, B: 2, C: 8 };

  for (let i &#61; 0; i &lt; sequence.length; i&#43;&#43;) {
    const need &#61; 1.25 * dict[sequence[i]];
    for (let j &#61; 0; j &lt; n; j&#43;&#43;) {
      if (boardCard[j] &gt;&#61; need) {
        boardCard[j] -&#61; need;
        break;
      }
    }
  }

  boardCard.forEach((remain) &#61;&gt; {
    unUsed &#61; remain / 1.25;
    used &#61; m - unUsed;
    console.log(
      new Array(used).fill(1).join(&#34;&#34;) &#43; new Array(unUsed).fill(0).join(&#34;&#34;)
    );
  });
}
</code></pre> 
<p></p> 
<h4>Java算法源码</h4> 
<pre><code class="language-java">import java.util.Arrays;
import java.util.HashMap;
import java.util.Scanner;

public class Main {
  public static void main(String[] args) {
    Scanner sc &#61; new Scanner(System.in);

    int m &#61; sc.nextInt();
    int n &#61; sc.nextInt();
    String sequence &#61; sc.next();

    getResult(m, n, sequence);
  }

  public static void getResult(int m, int n, String sequence) {
    double[] boardCard &#61; new double[n];
    Arrays.fill(boardCard, m * 1.25);

    HashMap&lt;Character, Integer&gt; dict &#61; new HashMap&lt;&gt;();
    dict.put(&#39;A&#39;, 1);
    dict.put(&#39;B&#39;, 2);
    dict.put(&#39;C&#39;, 8);

    for (int i &#61; 0; i &lt; sequence.length(); i&#43;&#43;) {
      double need &#61; 1.25 * dict.get(sequence.charAt(i));
      for (int j &#61; 0; j &lt; n; j&#43;&#43;) {
        if (boardCard[j] &gt;&#61; need) {
          boardCard[j] -&#61; need;
          break;
        }
      }
    }

    for (int i &#61; 0; i &lt; n; i&#43;&#43;) {
      int unUsed &#61; (int) (boardCard[i] / 1.25);
      int used &#61; m - unUsed;

      StringBuilder sb &#61; new StringBuilder();
      for (int j &#61; 0; j &lt; used; j&#43;&#43;) {
        sb.append(1);
      }
      for (int k &#61; 0; k &lt; unUsed; k&#43;&#43;) {
        sb.append(0);
      }
      System.out.println(sb);
    }
  }
}
</code></pre> 
<p></p> 
<h4>Python算法源码</h4> 
<pre><code class="language-python"># 输入获取
m &#61; int(input())
n &#61; int(input())
sequence &#61; input()


# 算法入口
def getResult(m, n, sequence):
    boardCard &#61; [m * 1.25] * n
    mapping &#61; {&#34;A&#34;: 1, &#34;B&#34;: 2, &#34;C&#34;: 8}

    for i in range(len(sequence)):
        need &#61; 1.25 * mapping[sequence[i]]
        for j in range(n):
            if boardCard[j] &gt;&#61; need:
                boardCard[j] -&#61; need
                break

    for remain in boardCard:
        unUsed &#61; int(remain / 1.25)
        used &#61; m - unUsed
        print(&#39;1&#39; * used &#43; &#39;0&#39; * unUsed)


# 算法调用
getResult(m, n, sequence)
</code></pre>
                </div>
        </div>
        <div id="treeSkill"></div>
        <div id="blogExtensionBox" style="width:400px;margin:auto;margin-top:12px" class="blog-extension-box"></div>
    <script>
  $(function() {
    setTimeout(function () {
      var mathcodeList = document.querySelectorAll('.htmledit_views img.mathcode');
      if (mathcodeList.length > 0) {
        for (let i = 0; i < mathcodeList.length; i++) {
          if (mathcodeList[i].naturalWidth === 0 || mathcodeList[i].naturalHeight === 0) {
            var alt = mathcodeList[i].alt;
            alt = '\\(' + alt + '\\)';
            var curSpan = $('<span class="img-codecogs"></span>');
            curSpan.text(alt);
            $(mathcodeList[i]).before(curSpan);
            $(mathcodeList[i]).remove();
          }
        }
        MathJax.Hub.Queue(["Typeset",MathJax.Hub]);
      }
    }, 1000)
  });
</script>
</div></html>